package main.leetcode.clockin.June;

import java.util.*;

/**
 * 126. 单词接龙 II
 *
 * <p>给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
 *
 * <p>每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
 *
 * <p>如果不存在这样的转换序列，返回一个空列表。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord
 * 是非空的，且二者不相同。
 *
 * <p>示例 1:<br>
 * 输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]<br>
 * 输出: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
 *
 * <p>示例 2:<br>
 * 输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]<br>
 * 输出: []<br>
 * 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
 */
public class day7 {
    public static void main(String[] args) {
        List<String> wordList1 = new ArrayList<>();
        Collections.addAll(wordList1, "hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(new Solution2().findLadders("hit", "cog", wordList1));

        List<String> wordList2 = new ArrayList<>();
        Collections.addAll(wordList2, "rex", "ted", "tex", "tad", "tax");
        System.out.println(new Solution2().findLadders("red", "tax", wordList2));
    }

    private static class Solution1 {

        public List<List<String>> findLadders(
                String beginWord, String endWord, List<String> wordList) {
            List<List<String>> res = new ArrayList<>();

            // 画图
            HashMap<String, HashSet<String>> graph = new HashMap<>();
            if (!creGraph(graph, beginWord, endWord, wordList)) {
                // false 说明无法转变成最后一个单词
                return res;
            }

            // bfs找路
            Deque<String> path = new ArrayDeque<>();
            path.addLast(beginWord);
            dfs(beginWord, endWord, graph, path, res);
            return res;
        }

        private void dfs(
                String beginWord,
                String endWord,
                HashMap<String, HashSet<String>> graph,
                Deque<String> path,
                List<List<String>> res) {
            // 到达终点
            if (beginWord.equals(endWord)) {
                res.add(new ArrayList<>(path));
                return;
            }

            HashSet<String> successors = graph.get(beginWord);
            if (successors == null) {
                return;
            }
            // 回溯查找
            for (String successor : successors) {
                path.addLast(successor);
                dfs(successor, endWord, graph, path, res);
                path.removeLast();
            }
        }

        /**
         * 创建无向图
         *
         * @param graph 图
         * @param beginWord 开始单词
         * @param endWord 结束单词
         * @param wordList 单词列表
         * @return 是否到达最后一个单词
         */
        private boolean creGraph(
                HashMap<String, HashSet<String>> graph,
                String beginWord,
                String endWord,
                List<String> wordList) {
            boolean reachEnd = false;

            // 记录已访问单词（一定要等同层单词都遍历过再将后继单词加入isVisited集，理由参考第一个例子的cog）
            HashSet<String> isVisited = new HashSet<>();
            isVisited.add(beginWord);

            // queue存储访问序列
            Queue<String> queue = new LinkedList<>();
            queue.add(beginWord);

            String pre;
            // pre的后继节点集
            HashSet<String> successors = new HashSet<>();
            while (!queue.isEmpty()) {
                // 记录当前队列长度，目的是为了在遍历完同一层的单词后再将单词加入isVisited集
                int curSizeOfQueue = queue.size();
                // 遍历同层单词
                for (int i = 0; i < curSizeOfQueue; ++i) {
                    pre = queue.poll();
                    // 遍历字典表
                    for (String s : wordList) {
                        if (isVisited.contains(s)) {
                            continue;
                        }
                        // 后继(仅有一个字符不同)加入后继集，加入无向图
                        if (compare(pre, s)) {
                            if (s.equals(endWord)) {
                                reachEnd = true;
                            }
                            queue.add(s);
                            successors.add(s);
                            graph.computeIfAbsent(pre, str -> new HashSet<>());
                            graph.get(pre).add(s);
                        }
                    }
                }
                // 已经到达最后一个单词所在层，那么再往后路径只会更长，所以提前break
                if (reachEnd) {
                    break;
                }
                isVisited.addAll(successors);
                successors.clear();
            }
            return reachEnd;
        }

        /**
         * 比较两单词是否仅有一个字符的差别
         *
         * @param pre 单词1
         * @param s 单词2
         * @return boolean
         */
        private boolean compare(String pre, String s) {
            int n = pre.length();
            char[] pres = pre.toCharArray();
            char[] ss = s.toCharArray();
            boolean firstDiff = false;
            for (int i = 0; i < n; ++i) {
                if (pres[i] != ss[i] && !firstDiff) {
                    firstDiff = true;
                } else if (pres[i] != ss[i]) {
                    return false;
                }
            }
            return firstDiff;
        }
    }

    private static class Solution2 {

        public List<List<String>> findLadders(
                String beginWord, String endWord, List<String> wordList) {
            List<List<String>> res = new ArrayList<>();

            // 直接使用wordList来遍历寻找的话会超时，所以改用set
            HashSet<String> wordSet = new HashSet<>(wordList);

            // 画图
            HashMap<String, HashSet<String>> graph = new HashMap<>();
            if (!creGraph(graph, beginWord, endWord, wordSet)) {
                // false 说明无法转变成最后一个单词
                return res;
            }

            // bfs找路
            Deque<String> path = new ArrayDeque<>();
            path.addLast(beginWord);
            dfs(beginWord, endWord, graph, path, res);
            return res;
        }

        private void dfs(
                String beginWord,
                String endWord,
                HashMap<String, HashSet<String>> graph,
                Deque<String> path,
                List<List<String>> res) {
            // 到达终点
            if (beginWord.equals(endWord)) {
                res.add(new ArrayList<>(path));
                return;
            }

            HashSet<String> successors = graph.get(beginWord);
            if (successors == null) {
                return;
            }
            // 回溯查找
            for (String successor : successors) {
                path.addLast(successor);
                dfs(successor, endWord, graph, path, res);
                path.removeLast();
            }
        }

        /**
         * 创建无向图
         *
         * @param graph 图
         * @param beginWord 开始单词
         * @param endWord 结束单词
         * @param wordSet 单词列表
         * @return 是否到达最后一个单词
         */
        private boolean creGraph(
                HashMap<String, HashSet<String>> graph,
                String beginWord,
                String endWord,
                HashSet<String> wordSet) {
            boolean reachEnd = false;

            // 记录已访问单词（一定要等同层单词都遍历过再将后继单词加入isVisited集，理由参考第一个例子的cog）
            HashSet<String> isVisited = new HashSet<>();
            isVisited.add(beginWord);

            // queue存储访问序列
            Queue<String> queue = new LinkedList<>();
            queue.add(beginWord);

            String pre;
            // pre的后继节点集
            HashSet<String> successors = new HashSet<>();
            while (!queue.isEmpty()) {
                // 记录当前队列长度，目的是为了在遍历完同一层的单词后再将单词加入isVisited集
                int curSizeOfQueue = queue.size();
                // 遍历同层单词
                for (int i = 0; i < curSizeOfQueue; ++i) {
                    pre = queue.poll();
                    int n = pre.length();
                    char[] chars = pre.toCharArray();
                    for (int k = 0; k < n; ++k) {
                        char origin = chars[k];
                        for (char j = 'a'; j <= 'z'; ++j) {
                            if (chars[k] == j) {
                                continue;
                            }
                            chars[k] = j;
                            String s = new String(chars);
                            if (wordSet.contains(s) && !isVisited.contains(s)) {
                                if (s.equals(endWord)) {
                                    reachEnd = true;
                                }
                                queue.add(s);
                                successors.add(s);
                                graph.computeIfAbsent(pre, str -> new HashSet<>());
                                graph.get(pre).add(s);
                            }
                        }
                        chars[k] = origin;
                    }
                }
                // 已经到达最后一个单词所在层，那么再往后路径只会更长，所以提前break
                if (reachEnd) {
                    break;
                }
                isVisited.addAll(successors);
                successors.clear();
            }
            return reachEnd;
        }
    }
}
